1. Field of the Invention
The present invention relates to a soft decision maximum likelihood decoding method, and apparatus, and in particular to a soft decision maximum likelihood decoding method, and apparatus, which is applied to a mobile radio telecommunication system having a signal level varied by fading.
2. Description of the Related Art
In recent years, error correcting techniques for correcting errors caused in transmission data during transmission have been widely used in many fields in order to improve the reliability of data transmission. Especially, a scheme of coding data by using convolutional codes and performing maximum likelihood decoding by using Viterbi decoding has a high error correcting capability, and the scheme is applied to various fields.
As a known example concerning a Viterbi decoder which is famous as a maximum likelihood decoder, there is a decoder described in JP-A-62-243431 entitled "maximum likelihood decoder". In preparation for description of the present invention, the principle of Viterbi decoding will now be described by taking convolutional codes with a coding rate of 1/2 and a constraint length of K=3 as an example.
The generator polynomials for convolutional codes with the coding rate of 1/2 and the constraint length of K=3 is represented by the following expressions (1). ##EQU1##
In the expressions (1), D represents a delay operator of one unit time and addition is performed by using an exclusive OR. The convolutional coder of the expression (1) is configured as shown in FIG. 1. In FIG. 1, numerals 1 and 2 denote delay elements, which form a 2-bit shift register. Numerals 3, 4 and 5 denote exclusive OR gates. By two bits n and m stored in the shift register, the operation state of the coder is represented. Each time an information bit x is inputted to the shift register, a transition is made in the state of the coder and two bits (g.sub.0, g.sub.1) are sent out as a transmission code.
An error train is added to this on a transmission channel, and a received train is thus obtained. In a decoder, the state transition of the coder is estimated from this received train, a state transition having maximum likelihood is selected, and an information train is estimated therefrom.
When input information of k bits is coded into n bits, the coding rate R is represented by R=k/n. Assuming that the number of stages of the delay elements is m, the constraint length K is represented by K=(m+1)k.
The principle of operation of the Viterbi decoder will now be described in more detail by referring to FIG. 2. FIG. 2B is a diagram called a trellis diagram, which represents the allowed state transitions over plural time units. Transitions between time t.sub.m and time t.sub.m+1 are represented as shown in FIG. 2A. In FIG. 2A, x/g.sub.0,g.sub.1 indicated on a transition branch represents an information bit x and values of outputted codes g.sub.0 and g.sub.1 at the time when the coder has made its transition. If an information bit 0 is inputted in a state 10, for example, a code 11 is outputted and a transition to state 00 is made. It is now assumed that 1, 0, 0, 1, 1, 1, 0, 1, (0, 0) are successively inputted to the shift register as an information bit train x. Initial values of the shift register are set to (0, 0). Stopping bits (0, 0) for clearing the shift register are added to the end of the information bit train. Deriving the transmission code train by referring to FIG. 1, we get 11, 01, 11, 11, 10, . . . . Paths for the state transitions are represented by thick solid lines in FIG. 2B. On the receiving side, a received train 11, 01, 01, 11, 11, . . . resulting from addition of an error train 00, 00, 10, 00, 01, . . . caused in the transmission train to the transmission train is received. In the decoder, all state transitions which can be assumed by the coder are traced by referring to the received train and the state transition of the coder is estimated.
In order to quantitatively represent certainty of a state transition, a "likelihood metric" will now be defined. That is to say, the Hamming distance between the received code (r.sub.0, r.sub.1) and a candidate code is defined as a likelihood metric of the branch. When the received code is 01, for example, the (branch) likelihood metric of each candidate code is given as shown in Table 1.
TABLE 1 ______________________________________ CANDIDATE CODE 00 01 10 11 BRANCH LIKELIHOOD 1 0 2 1 METRIC ______________________________________
The result obtained by successively adding branch likelihood metric values of state transitions up to each state is referred to as "state likelihood metric". In the example shown in FIG. 2, a transition is made from the initial state 00 at time 0 to the state 00 or state 01. Since the output code of the transition from the state 00 to the state 00 is 00 whereas the received code at this time is 11, the branch likelihood metric thereof is 2. In the same way, since the output code of the transition from the state 00 to the state 01 is 11 whereas the received code at this time is 11, the branch likelihood metric thereof is 0. As a result, state likelihood metric values of the state 00 and state 01 at time point 1 are 2 and 0, respectively. In FIG. 2B, a numeral representing the state likelihood metric at each time point is indicated next to the circle indicating the state. On the basis of branch likelihood metric values accompanying possible state transitions from the time point 1 to time point 2, values 3, 3, 0 and 2 are derived as state likelihood metric values of states 00, 01, 10 and 11 at the time point 2, respectively. Furthermore, branch likelihood metric values of possible state transitions from the time point 2 to the time point 3 are derived. On and after this time point, there are two branches leading to each state. In the maximum likelihood decoding process, a branch on a path having a smaller likelihood metric (i.e. a more likely branch) is selected and the other branch is discarded. In FIG. 2B, selected branches are represented by solid lines whereas discarded branches are represented by broken lines. Branch likelihood metric values of selected branches are added as state likelihood metric values. To the state 00 at time point 5, for example, a transition is made from the state 00 or the state 10 at time point 4. The sum of the state likelihood metric and branch likelihood metric become 5 and 2, respectively. A transition from the state 10 having a smaller likelihood metric value is selected. The state likelihood metric of the state 00 at the time point 5 becomes 2. In this way, a coding train concerning a series of branches finally selected (i.e., a surviving path) is a coding train estimated to have a maximum likelihood by the Viterbi decoder.
In FIGS. 2A and 2B, an example having a very high error rate is shown. Among 20 bits, seven bits are erroneous (i.e., error rate is 0.35). In such a state having a high error rate, it is difficult to reduce decoding errors even with maximum likelihood decoding. Writing the received code train in time series by tracing states each having a minimum state likelihood metric value at time point 10 in the example of FIG. 2B, we get 11, 01, 10, 11, 00, 00, 11, 10, 01 and 10. It is understood that as many as eight erroneous bits have been caused from the transmission code train. Such a situation hardly occurs, but it can be sufficiently supposed that such a situation would occur locally in burst errors and some measure is needed.
For the subsequent description, the configuration of the Viterbi decoder is shown in FIG. 3. In FIG. 3, numeral 31 denotes a branch likelihood metric calculation circuit, 32 an addition comparison selection circuit, 33 a state likelihood metric memory, 34 a path memory, and 35 a maximum likelihood decision circuit. According to the method shown in Table 1, the branch likelihood metric calculation circuit 31 derives certainty of state transition (branch likelihood metric) from the received signal. The addition comparison selection circuit 32 derives a new state likelihood metric by adding the branch likelihood metric value of a possible state transition to the state likelihood metric value at the immediately preceding time point stored in the state likelihood metric memory 33. The addition comparison selection circuit 32 compares state likelihood metric values of a plurality of state transitions leading to one state, and selects a transition having a minimum value out of them. Then the addition comparison selection circuit 32 updates contents of the state likelihood metric memory 33 by adopting the state likelihood metric of the selected transition as a new state likelihood metric. At the same time, the addition comparison selection circuit 32 sends information j(i) of the selected transition to the path memory 34, where j(i) represents a transition from state j to state i. The path memory 34 stores this transition information j(i) or state numbers of the transition in a series. The maximum likelihood circuit 35 derives a result of decoding from the state transition selected and left at the final time point.
In the above described maximum likelihood decoding scheme, a method called hard decision is used for calculation of branch likelihood metric. In the hard decision, the reliability of the transmission code train is measured with a Hamming distance of the code train as defined in Table 1. On the other hand, there is a soft decision scheme in which the reliability of the transmission code is given by the Euclidean distance of the amplitude value of the received signal. This is shown in FIG. 4.
FIG. 4 gives a soft decision likelihood metric for a one-dimensional (one bit) code. In case of two-dimensional (two-bit) code, it may be applied to each bit and results may be added together. The received signal level +V corresponds to code "0", and -V corresponds to code "1". In FIG. 4, a likelihood metric for code "0" is represented. As this likelihood metric, values 0 to 16 are assigned according to the received amplitude value. That is to say, if a signal having an amplitude as represented by an illustrated received signal amplitude value A is received, the likelihood metric at the time of the hard decision becomes 0. In the hard decision, it is known that the received code is near the code "0", but its certainty cannot be judged with sufficient precision. 0n the other hand, 6 is given as the likelihood metric in soft decision. Since this is a value close to 8 (middle point between two code levels), it can be judged to be close to the code "0" but is low in reliability. The likelihood metric for the code "1" has a slope symmetrical to the likelihood metric for the code "0" with respect to the vertical axis of FIG. 4.
It is known that introduction of the soft decision likelihood metric as shown in FIG. 4 further improves the performance of the maximum likelihood decoding scheme. However, improvement of performance due to soft decision is limited to transmission channel on which the received signal level is nearly constant and random errors are caused. On a transmission channel having a received signal level abruptly changed by fading as in mobile radio communication systems, concentrated errors occur in a burst when the received signal level has dropped. This is equivalent to a very high rise in local error rate. In such a case, the Viterbi decoder loses its error correcting capability.
This situation will now be described by referring to a trellis diagram of a Viterbi decoder using a soft decision likelihood metric as shown in FIG. 5. In FIG. 5, a soft decision likelihood metric has been applied to the example of FIG. 2. That is to say, a transmission code "0" is associated with a received level +7 whereas transmission code "1" is associated with a received level -8. Therefore, a transmission code (0, 1) corresponds to a received level (7, -8). Values of error trains are also represented by levels. Levels of -8 or less and +8 or more are judged to be erroneous. For example, therefore, an error pattern (9, -5) corresponds to an error pattern (1, 0) of FIG. 2. The actual received level is the sum of the signal level value of a transmission code and the error value. With respect to a received code, the soft decision branch likelihood metric of each transmission code is given by the sum of signal level differences of respective columns between those codes. For example, when the received level is (1, 2), the branch likelihood metric is given as shown in Table 2.
TABLE 2 ______________________________________ CODE 00 01 10 11 (BINARY NUMBER) (7, 7) (7, -8) (-8, 7) (-8, -8) BRANCH LIKELIHOOD 11 16 14 19 METRIC (DECIMAL) ______________________________________
The result obtained by conducting maximum likelihood decoding processing in the same way as FIG. 2 by using the soft decision branch likelihood metric is shown in FIG. 5. Selected branches are represented by solid lines, whereas discarded branches are represented by broken lines. A numeral indicated next to a circle representing a state indicates the value of the state likelihood metric at each time point. Furthermore, state transitions corresponding to the transmission code train are represented by thick solid lines. As understood from FIG. 5, a transition corresponding to the transmission code train is not selected and is broken between time points 7 and 8. That is to say, it is understood that error correction is difficult even if the soft decision scheme is used, in the case that errors locally concentrate and the error rate becomes momentarily high as shown in FIG. 5.